package com.lwl.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/3/19 20:24
 */
public class Code187FindRepeatedDnaSequences {
    public static void main(String[] args) {
        List<String> list = findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
        for (String s : list) {
            System.out.println(s);
        }
    }

    public static List<String> findRepeatedDnaSequences(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int right = 0; right < chars.length; right++) {
            if (!isACGT(chars[right]) && right + 1 < chars.length) {
                left = right + 1;
            }
            if (right - left + 1 > 10) {
                left++;
            }
            if (right - left + 1 == 10) {
                String substring = s.substring(left, right + 1);
                map.put(substring, map.getOrDefault(substring, 0) + 1);
            }
        }
        return map.entrySet().stream().filter(entry -> entry.getValue() > 1).map(Map.Entry::getKey).collect(Collectors.toList());
    }

    private static boolean isACGT(char c) {
        return c == 'A' || c == 'C' || c == 'G' || c == 'T';
    }
}
